package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/7 8:43
 */
public class C81 {

    // https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
    // 暴力解
    public static boolean search(int[] nums, int target) {
        for (int num : nums) {
            if (num == target) {
                return true;
            }
        }
        return false;
    }

    // 先找到k点.
    public static boolean search2(int[] nums, int target) {
        int k = 0;
        for (; k + 1 < nums.length && nums[k + 1] >= nums[k]; k++) {
            if (target == nums[k]) {
                return true;
            }
        }
        k++;
        // k此时为最小值的下标, k-1等于最大值的下标.
        // 或者k越界代表从小到大.
        int l, r;
        if (k == nums.length) {
            // 上边看过一遍了
//            l = 0;
//            r = k-1;
            return nums[k-1] == target;
        }else if (target >= nums[0] && target <= nums[k-1]) {
            // 左侧找, 但左边已经看过一遍了
//            l = 0;
//            r = k - 1;
            return nums[k-1] == target;
        } else if (target <= nums[nums.length - 1]) {
            // 右侧找
            l = k;
            r = nums.length - 1;
        } else {
            return false;
        }
        return binarySearch(nums, l, r, target);
    }

    private static boolean binarySearch(int[] nums, int l, int r, int target) {
        int m;
        while (l <= r) {
            m = l + ((r - l) >> 1);
            if (nums[m] == target) {
                return true;
            } else if (target < nums[m]) {
                // 左
                r = m - 1;
            } else {
                // 右
                l = m + 1;
            }
        }
        return false;
    }


    public static void main(String[] args) {
//        int[] nums = {1};
        int[] nums = {2,2,2,3,2,2,2};
        int target = 3;
        boolean ans1 = search(nums, target);
        boolean ans2 = search2(nums, target);


        System.out.println(ans1);
        System.out.println(ans2);
    }

}
